#include "../tools.h"


class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<ListNode*> st;

        ListNode* p = head;
        while(p != nullptr){
            st.push(p);
            p = p->next;
        }

        ListNode prehead(0, head);
        p = &prehead;
        ListNode* t;
        while(!st.empty()){
            t = st.top(); st.pop();
            p->next = t;
            t->next = nullptr;
            p = t;
        }
        return prehead.next;
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    int arr[] = {1,2,3,4,5};
    int size = sizeof(arr) / sizeof(int);

    ListNode* head = create_list(arr, size);
    show(head);

    head = sol.reverseList(head);
    show(head);

    return 0;
}
